import time
import math
import random
import string

class GA:
    mutation_prob = 0.025
    elite_prob = 0.1
    max_iteration = 100
    population_size = 10240
    target = "applegooglemicrosoft"

    def InitPopulation(self):
        self.mPopulation = list()
        for i in range(GA.population_size):
            self.mPopulation.append(string.join(random.sample([chr(i) for i in range(97, 123)], len(GA.target))).replace(' ', ''))
        #end for
    
    def FitnessFn(self, individual):
        fitness = 0
        for ipos in range(0, len(GA.target)):
            fitness += abs(ord(individual[ipos]) - ord(GA.target[ipos]))
        return fitness
        
    def CrossoverFn(self, p1, p2):
        ipos = random.randint(1, len(GA.target)-2)
        return p1[0:ipos] + p2[ipos:]
    
    def MutationFn(self, p):
        ipos = random.randint(0, len(GA.target)-1)
        c = random.choice([chr(i) for i in range(97, 123)])
        return p[0:ipos] + c + p[(ipos+1):]
    
    def Run(self):
        self.InitPopulation()
        
        top_elite = int(GA.elite_prob * GA.population_size)
        
        for i in range(GA.max_iteration):
            print i
            individual_scores = [(self.FitnessFn(v), v) for v in self.mPopulation]
            individual_scores.sort()
            
            ranked_individual = [v for (s, v) in individual_scores]
            
            # population winner
            self.mPopulation = ranked_individual[0:top_elite]
            
            # add mutated and bred forms of the winner
            while len(self.mPopulation) < GA.population_size:
                if random.random() < GA.mutation_prob:
                    # mutation
                    c = random.randint(0, top_elite)
                    self.mPopulation.append(self.MutationFn(ranked_individual[c]))
                else:
                    # crossover
                    c1 = random.randint(0, top_elite)
                    c2 = random.randint(0, top_elite)
                    self.mPopulation.append(self.CrossoverFn(ranked_individual[c1], ranked_individual[c2]))
                #end if
            #end while
            
            # stop before
            if individual_scores[0][0] == 0:
                return individual_scores[0][1]
        #end for
        return individual_scores[0][1]
#end class


def main():
    t = GA()
    print t.Run()
    

if __name__ == "__main__":
    start = time.clock()
    main()
    elapsed = (time.clock() - start)
    print "Time used: %.2f" % elapsed